{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #彩灯装饰记录 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: decorateRecord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #彩灯装饰记录 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一棵圣诞树记作根节点为 <code>root</code> 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照如下规则记录彩灯装饰结果：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第一层按照从左到右的顺序记录</li>\n",
    "\t<li>除第一层外每一层的记录顺序均与上一层相反。即第一层为从左到右，第二层为从右到左。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694758674-XYrUiV-%E5%89%91%E6%8C%87%20Offer%2032%20-%20I_%E7%A4%BA%E4%BE%8B1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [8,17,21,18,null,null,6]\n",
    "<strong>输出：</strong>[[8],[21,17],[18,6]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>节点总数 &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,17,21,18,null,null,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        queue = deque([root])\n",
    "        total_ans = []\n",
    "        while queue:\n",
    "            level_len = len(queue)\n",
    "            ans = []\n",
    "            for _ in range(level_len):\n",
    "                curr = queue.popleft()\n",
    "                ans.append(curr.val)\n",
    "                if curr.left:\n",
    "                    queue.append(curr.left)\n",
    "                if curr.right:\n",
    "                    queue.append(curr.right)\n",
    "            total_ans.append(ans)\n",
    "\n",
    "        return total_ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        queue.append((root, 0))\n",
    "        ans = []\n",
    "        last_index = -1\n",
    "\n",
    "        while queue:\n",
    "            node, index = queue.popleft()\n",
    "            \n",
    "            if index != last_index:\n",
    "                ans.append([node.val])\n",
    "                last_index = index\n",
    "            else:\n",
    "                ans[-1].append(node.val)\n",
    "            \n",
    "            if node.left is not None:\n",
    "                queue.append((node.left, index + 1))\n",
    "            if node.right is not None:\n",
    "                queue.append((node.right, index + 1))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "      if not root:return []\n",
    "      que, ans = collections.deque(), []\n",
    "      que.append(root)\n",
    "      while que:\n",
    "        tmp = []\n",
    "        i = len(que)-1\n",
    "        while i>=0:\n",
    "          node = que.popleft()\n",
    "          tmp.append(node.val)\n",
    "          if node.left:que.append(node.left)\n",
    "          if node.right:que.append(node.right)\n",
    "          i -= 1\n",
    "        ans.append(tmp)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        q=collections.deque()\n",
    "        q.append(root)\n",
    "        q.append(None)\n",
    "        ans,sub_ans=[],[]\n",
    "        while True:\n",
    "            node=q.popleft()\n",
    "            if node:\n",
    "                sub_ans.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            else:\n",
    "                ans.append(sub_ans)\n",
    "                if len(q)==0: \n",
    "                    break\n",
    "                else:\n",
    "                    sub_ans=[]\n",
    "                    q.append(None)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            level = []\n",
    "            for _ in range(sz):\n",
    "                cur = q.popleft()\n",
    "                level.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            res.append(level)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        stack = collections.deque()\n",
    "        stack.append(root)\n",
    "        while stack :\n",
    "            nexti = []\n",
    "            for _ in range(len(stack)) :\n",
    "                node = stack.popleft()\n",
    "                nexti.append(node.val)\n",
    "                if node.left :\n",
    "                    stack.append(node.left)\n",
    "                if node.right :\n",
    "                    stack.append(node.right)\n",
    "            ans.append(nexti)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tem = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tem.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tem)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "      if not root:return []\n",
    "      que, ans = collections.deque(), []\n",
    "      que.append(root)\n",
    "      while que:\n",
    "        tmp = []\n",
    "        for _ in range(len(que)):\n",
    "          node = que.popleft()\n",
    "          tmp.append(node.val)\n",
    "          if node.left:que.append(node.left)\n",
    "          if node.right:que.append(node.right)\n",
    "        ans.append(tmp)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            this = []\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                if cur.left: q.append(cur.left)\n",
    "                if cur.right: q.append(cur.right)\n",
    "                this.append(cur.val)\n",
    "            ans.append(this)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tem = []\n",
    "            for  _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tem.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tem)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        deuqe = [root]\n",
    "        res = []\n",
    "        flag = True\n",
    "        while deuqe:\n",
    "            tmp = []\n",
    "            for i in range(len(deuqe)):\n",
    "                node = deuqe.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    deuqe.append(node.left)\n",
    "                if node.right:\n",
    "                    deuqe.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\tdef decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\t\tif not root:\n",
    "\t\t\treturn []\n",
    "\t\tnode_list = []\n",
    "\t\tnode_list.append(root)\n",
    "\t\tresult = []\n",
    "\t\twhile node_list:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tfor i in range(len(node_list)):\n",
    "\t\t\t\tnode = node_list.pop(0)\n",
    "\t\t\t\ttemp.append(node.val)\n",
    "\t\t\t\tif node.left:\n",
    "\t\t\t\t\tnode_list.append(node.left)\n",
    "\t\t\t\tif node.right:\n",
    "\t\t\t\t\tnode_list.append(node.right)\n",
    "\t\t\tresult.append(temp)\n",
    "\t\treturn result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            curLevelArr = []\n",
    "            curLevelLen = len(queue)\n",
    "            for i in range(curLevelLen):\n",
    "                node = queue.popleft()\n",
    "                curLevelArr.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(curLevelArr)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            layer = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(layer)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root :return []\n",
    "        res=[]\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            new_stack=[]\n",
    "            res_line=[]\n",
    "            for _ in range(len(stack)):\n",
    "                cur=stack.pop()\n",
    "                res_line.append(cur.val)\n",
    "                if cur.left: stack=[cur.left]+stack\n",
    "                if cur.right: stack=[cur.right]+stack\n",
    "            res.append(res_line)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,q=[],deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp=[]\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                temp.append(node.val)   \n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,q=[],deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp=[]\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                temp.append(node.val)   \n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for x in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        re=[]\n",
    "        stack=[[root]]\n",
    "        while stack:\n",
    "            box=[]\n",
    "            nodes=stack[-1]\n",
    "            rbox=[]\n",
    "            for node in nodes:\n",
    "                if node:\n",
    "                    rbox.append(node.val)\n",
    "                    if node.left:box.append(node.left)\n",
    "                    if node.right:box.append(node.right)\n",
    "            stack=stack[1:]\n",
    "            if box:\n",
    "                stack.append(box)\n",
    "            if rbox:re.append(rbox)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\tdef decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\t\tif not root:\n",
    "\t\t\treturn []\n",
    "\t\tnode_list = []\n",
    "\t\tnode_list.append(root)\n",
    "\t\tresult = []\n",
    "\t\twhile node_list:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tfor i in range(len(node_list)):\n",
    "\t\t\t\tnode = node_list.pop(0)\n",
    "\t\t\t\ttemp.append(node.val)\n",
    "\t\t\t\tif node.left:\n",
    "\t\t\t\t\tnode_list.append(node.left)\n",
    "\t\t\t\tif node.right:\n",
    "\t\t\t\t\tnode_list.append(node.right)\n",
    "\t\t\tresult.append(temp)\n",
    "\t\treturn result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # 注意 root=[]的情况\n",
    "        if not root: return []\n",
    "        result, queue = [], collections.deque()\n",
    "\n",
    "        queue.append(root)\n",
    "        \n",
    "        while queue:\n",
    "            temp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            result.append(temp)\n",
    "    \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        else:\n",
    "            queue = [root]\n",
    "            output = []\n",
    "            while len(queue) != 0:\n",
    "                temp = []\n",
    "                nxt = []\n",
    "                for i in range(len(queue)):\n",
    "                    temp.append(queue[i].val)\n",
    "                    if queue[i].left:               \n",
    "                        nxt.append(queue[i].left)\n",
    "                    if queue[i].right:\n",
    "                        nxt.append(queue[i].right)\n",
    "#                queue.pop(0)\n",
    "                queue = nxt\n",
    "                output.append(temp)\n",
    "            return output\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> list[list[int]]:\n",
    "        res = []\n",
    "        deque = collections.deque()\n",
    "        if not root:\n",
    "            return []\n",
    "        deque.append(root)\n",
    "\n",
    "        while deque:\n",
    "            tmp = []\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    deque.append(node.left)\n",
    "                if node.right:\n",
    "                    deque.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res, tn = [], [root]\n",
    "        while tn:\n",
    "            r = []\n",
    "            for _ in range(len(tn)):\n",
    "                t = tn.pop(0)\n",
    "                r.append(t.val)\n",
    "\n",
    "                if t.left:\n",
    "                    tn.append(t.left)\n",
    "                if t.right:\n",
    "                    tn.append(t.right)\n",
    "            res.append(r)\n",
    " \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        list_a=[root]\n",
    "        res=[]\n",
    "        # print(len(list_a))\n",
    "        res.append(list_a)\n",
    "        level=0\n",
    "        # print(list_a)\n",
    "        # print(res)\n",
    "        while True:\n",
    "            list_a=[]\n",
    "            # print(res)\n",
    "            # print(res[level])\n",
    "            # print(len(res[level]))\n",
    "            for i in range(len(res[level])):\n",
    "                root=res[level][i]\n",
    "                # print('被执行了')\n",
    "                # tmp.append(root.val)\n",
    "                if root.left:\n",
    "                    list_a.append(root.left)\n",
    "                if root.right:\n",
    "                    list_a.append(root.right)\n",
    "                res[level][i]=root.val\n",
    "            if not list_a:\n",
    "                break\n",
    "            res.append(list_a)\n",
    "            level+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        else:\n",
    "            res,queue=[],collections.deque()\n",
    "            queue.append(root)\n",
    "            while queue:\n",
    "                tmp=[]\n",
    "                for i in range(len(queue)):\n",
    "                    j=queue.popleft()\n",
    "                    tmp.append(j.val)\n",
    "                    if j.left:\n",
    "                        queue.append(j.left)\n",
    "                    if j.right:\n",
    "                        queue.append(j.right)\n",
    "                res.append(tmp)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        queue = []\n",
    "        res = []\n",
    "        if not root:\n",
    "            return []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            n = len(queue)\n",
    "            for _ in range(n):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append([i for i in tmp])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res,queue=[],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            for _ in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                   queue.append(node.left)             \n",
    "                if node.right:\n",
    "                   queue.append(node.right)              \n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res, queue = [], collections.deque()\n",
    "        if root: queue.append(root)\n",
    "        while queue:\n",
    "            r = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                r.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(temp)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        ans=[]\n",
    "        while len(q) !=0:\n",
    "            nodes=[]\n",
    "            tps=[]\n",
    "            while len(q)!=0:\n",
    "                node=q.popleft()\n",
    "                nodes.append(node)\n",
    "                tps.append(node.val)\n",
    "            ans.append(tps)\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        row, res, queue = 0, [], collections.deque()\n",
    "        queue.append((0,root))\n",
    "        tmp = []\n",
    "        while queue:\n",
    "            if queue[0][1].left: queue.append((queue[0][0] + 1, queue[0][1].left))\n",
    "            if queue[0][1].right: queue.append((queue[0][0] + 1, queue[0][1].right))\n",
    "            if queue[0][0] == row:\n",
    "                tmp.append(queue[0][1].val)\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp = [queue[0][1].val]\n",
    "                row += 1\n",
    "            queue.popleft()\n",
    "        res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:    return []\n",
    "        res, row_values = [], []\n",
    "        que = []\n",
    "        cur_last, next_last = root, None\n",
    "\n",
    "        que.append(root)\n",
    "        while len(que) != 0:\n",
    "            node = que.pop(0)\n",
    "            row_values.append(node.val)\n",
    "            \n",
    "            if node.left:\n",
    "                que.append(node.left)\n",
    "                next_last = node.left\n",
    "            if node.right:\n",
    "                que.append(node.right)\n",
    "                next_last = node.right\n",
    "\n",
    "            if node == cur_last:\n",
    "                cur_last = next_last\n",
    "                res.append(row_values.copy())\n",
    "                row_values.clear()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# root =\n",
    "#    [8,17,21,18,null,null,6]\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        \n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        re=[]\n",
    "        stack=[[root]]\n",
    "        while stack:\n",
    "            box=[]\n",
    "            nodes=stack[-1]\n",
    "            rbox=[]\n",
    "            for node in nodes:\n",
    "                if node:\n",
    "                    rbox.append(node.val)\n",
    "                    if node.left:box.append(node.left)\n",
    "                    if node.right:box.append(node.right)\n",
    "            stack=stack[1:]\n",
    "            if box:\n",
    "                stack.append(box)\n",
    "            if rbox:re.append(rbox)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        row, res, queue = 0, [], collections.deque()\n",
    "        queue.append((0,root))\n",
    "        tmp = []\n",
    "        while queue:\n",
    "            if queue[0][1].left: queue.append((queue[0][0] + 1, queue[0][1].left))\n",
    "            if queue[0][1].right: queue.append((queue[0][0] + 1, queue[0][1].right))\n",
    "            if queue[0][0] == row:\n",
    "                tmp.append(queue[0][1].val)\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp = [queue[0][1].val]\n",
    "                row += 1\n",
    "            queue.popleft()\n",
    "        res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], [root]\n",
    "        # queue = collections.deque([root])\n",
    "        while queue:\n",
    "            # node = queue.pop(0)\n",
    "            # 当前层打印循环\n",
    "            temp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                temp.append(node.val)\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp_q = []\n",
    "            new_res = []\n",
    "            while q:\n",
    "                top_node = q.pop(0)\n",
    "                if top_node.left:\n",
    "                    tmp_q.append(top_node.left)\n",
    "                if top_node.right:\n",
    "                    tmp_q.append(top_node.right)\n",
    "                new_res.append(top_node.val)\n",
    "            q = tmp_q\n",
    "            res.append(new_res)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        if not root:\n",
    "            return ans\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            layer=[]\n",
    "            for i in range(n):\n",
    "                node=q.popleft()\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(layer)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        queue=[]\n",
    "        if not root:\n",
    "            return []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            res.append([])\n",
    "            for i in range(length):\n",
    "                root=queue[0]\n",
    "                res[-1].append(root.val)\n",
    "                queue.remove(queue[0])\n",
    "                if root.left:\n",
    "                    queue.append(root.left)\n",
    "                if root.right:\n",
    "                    queue.append(root.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res, queue = [], deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res,queue=[[]],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            temp=[]\n",
    "            for _ in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                   queue.append(node.left)             \n",
    "                if node.right:\n",
    "                   queue.append(node.right)              \n",
    "            res.append(temp)\n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,queue = [],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right:queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        q1, q2 = [], []\n",
    "        if not root:\n",
    "            return []\n",
    "        q1 = [root]\n",
    "        res = []\n",
    "        while q1:\n",
    "            current = []\n",
    "            l = len(q1)\n",
    "            for i in range(l):\n",
    "                n = q1.pop(0)\n",
    "                if n:\n",
    "                    current.append(n.val)\n",
    "                    if n.left:q2.append(n.left)\n",
    "                    if n.right:q2.append(n.right)\n",
    "            res.append(current)\n",
    "            q1 = q2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root : return []\n",
    "        res , queue = [] , collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left : queue.append(node.left)\n",
    "                if node.right :queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res, tmpres, queue, tmp = [], [], deque(), deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            tmpres.append(node.val)\n",
    "            if node.left:\n",
    "                tmp.append(node.left)\n",
    "            if node.right:\n",
    "                tmp.append(node.right)\n",
    "            if not queue:   # 当层已清零\n",
    "                res.append(tmpres)\n",
    "                tmpres = []\n",
    "                while tmp:\n",
    "                    queue.append(tmp.popleft())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        from collections import deque\n",
    "        ret = []\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(n):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ret.append(tmp)\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res,queue=[],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        queue = [root]\n",
    "\n",
    "        while queue:\n",
    "            tmp_queue = []\n",
    "            tmp_res = []\n",
    "            while queue:\n",
    "                ptr = queue.pop(0)\n",
    "                if ptr:\n",
    "                    tmp_res.append(ptr.val)\n",
    "                    tmp_queue.append(ptr.left)\n",
    "                    tmp_queue.append(ptr.right)\n",
    "            queue = tmp_queue\n",
    "            if tmp_res:\n",
    "                res.append(tmp_res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        row, res, queue = 0, [], collections.deque()\n",
    "        queue.append((0,root))\n",
    "        tmp = []\n",
    "        while queue:\n",
    "            if queue[0][1].left: queue.append((queue[0][0] + 1, queue[0][1].left))\n",
    "            if queue[0][1].right: queue.append((queue[0][0] + 1, queue[0][1].right))\n",
    "            if queue[0][0] == row:\n",
    "                tmp.append(queue[0][1].val)\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "                tmp = [queue[0][1].val]\n",
    "                row += 1\n",
    "            queue.popleft()\n",
    "        res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right:queue.append(node.right)\n",
    "            if len(res) % 2 == 0:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                tmp.reverse()\n",
    "                res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            if len(res) % 2 == 0:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                res.append(tmp[::-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        if root is None:\n",
    "            return res\n",
    "        \n",
    "        node = root\n",
    "        cur_opts = [node]\n",
    "        next_opts = None\n",
    "        item = None\n",
    "        flag = False\n",
    "        while cur_opts:\n",
    "            next_opts = []\n",
    "            item = []\n",
    "            for node in cur_opts:\n",
    "                item.append(node.val)\n",
    "                if node.left is not None:\n",
    "                    next_opts.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    next_opts.append(node.right)\n",
    "            \n",
    "            if flag:\n",
    "                item.reverse()\n",
    "            res.append(item)\n",
    "            flag = not flag\n",
    "            cur_opts = next_opts\n",
    "        \n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, deque = [], collections.deque()\n",
    "        deque.append(root)\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if len(res) % 2 == 0: tmp.append(node.val) # 奇数层 -> 插入队列尾部\n",
    "                else: tmp.appendleft(node.val) # 偶数层 -> 插入队列头部\n",
    "                if node.left: deque.append(node.left)\n",
    "                if node.right: deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        cnt = 0\n",
    "        while queue:\n",
    "            cnt+=1\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            if cnt % 2 == 1: \n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                tmp.reverse()\n",
    "                res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root == [] or root == None:\n",
    "            return []\n",
    "        \n",
    "        # 创建两个队列\n",
    "        res = []\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        a = -1\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            \"\"\"\n",
    "            原本思路：根据a的不同值，将左右的添加顺序写反，发现是不对的\n",
    "            因为他要求的是这一层反过来，\n",
    "            如果只是左右反了，不管用的\n",
    "            17    18\n",
    "            | \\   | \\\n",
    "            1  2  3  4\n",
    "            如果17,18是从左到右边，\n",
    "            那下边的变成从右边到左边，那就形成了\n",
    "            开水还是从17开始，18结束，每一个节点都从右边到左边拿数据，就成2143\n",
    "            2 1 4 3 \n",
    "            \n",
    "            这里使用的列表，拿数据都是正向拿，这里在存储数据的时候，\n",
    "            根据不同的条件，在存储时选择正向存储列表还是把列表颠倒后存储。\n",
    "            \"\"\"\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if a == 1:\n",
    "                tmp = tmp[::-1]\n",
    "            res.append(tmp)\n",
    "            a = a * -1\n",
    "        return res            \n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,q=[],deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp=deque()\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                if len(res)%2==0:\n",
    "                    temp.append(node.val)\n",
    "                else:\n",
    "                    temp.appendleft(node.val)\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)         \n",
    "            res.append(list(temp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res,deque = [], collections.deque()\n",
    "        deque.append(root)\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if len(res)%2==0:tmp.append(node.val)\n",
    "                else :tmp.appendleft(node.val)\n",
    "                if node.left:deque.append(node.left)\n",
    "                if node.right:deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None: return []\n",
    "        deque, res, count = collections.deque(), [], 1\n",
    "        deque.append(root)\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "            for i in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if count & 1 == 1: tmp.append(node.val)\n",
    "                else: tmp.appendleft(node.val)\n",
    "                if node.left is not None:\n",
    "                    deque.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "            count += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res =[]\n",
    "        deque = collections.deque()\n",
    "        deque.append(root)\n",
    "        i=0\n",
    "        while deque:\n",
    "            cur = []\n",
    "            i +=1\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                cur.append(node.val)\n",
    "                if node.left:deque.append(node.left)\n",
    "                if node.right:deque.append(node.right)\n",
    "            if i%2 == 0:\n",
    "                cur.reverse()\n",
    "            res.append(cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        queue = [root]\n",
    "        ans = []\n",
    "        l = 0\n",
    "\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            l += 1\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if not l % 2:\n",
    "                    tmp.insert(0, cur.val)\n",
    "                else:\n",
    "                    tmp.append(cur.val)\n",
    "                if cur.left: queue.append(cur.left)\n",
    "                if cur.right: queue.append(cur.right)\n",
    "            ans.append(tmp)\n",
    "        return ans               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        queue = deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        flag = 1\n",
    "        while len(queue) is not 0:\n",
    "            temp_len = len(queue)\n",
    "            temp = []\n",
    "            for i in range(0,temp_len):\n",
    "                temp_node = queue.popleft()\n",
    "                if temp_node is not None:\n",
    "                    temp.append(temp_node.val)\n",
    "                    queue.append(temp_node.left)\n",
    "                    queue.append(temp_node.right)\n",
    "            if flag is 1:\n",
    "                res.append(temp)\n",
    "                flag = 0\n",
    "            else:\n",
    "                res.append(temp[::-1])\n",
    "                flag = 1\n",
    "                \n",
    "        return res[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        traversal = []\n",
    "        node_queue, level_queue = [root], [0]\n",
    "        current_level, head = -1, -1\n",
    "        while head < len(node_queue) - 1:\n",
    "            head += 1\n",
    "            if level_queue[head] != current_level:\n",
    "                traversal.append([])\n",
    "                current_level = level_queue[head]\n",
    "            traversal[-1].append(node_queue[head].val)\n",
    "            if node_queue[head].left is not None:\n",
    "                node_queue.append(node_queue[head].left)\n",
    "                level_queue.append(level_queue[head] + 1)\n",
    "            if node_queue[head].right is not None:\n",
    "                node_queue.append(node_queue[head].right)\n",
    "                level_queue.append(level_queue[head] + 1)\n",
    "        for i in range(len(traversal)):\n",
    "            if i % 2 == 1:\n",
    "                traversal[i].reverse()\n",
    "        return traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        level, queue = 1, deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            # 如果是偶数层，则反转下\n",
    "            if level % 2 == 0:\n",
    "                tmp.reverse()\n",
    "            res.append(tmp)\n",
    "            level += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,deque=[],collections.deque()\n",
    "        deque.append(root)\n",
    "        while deque:\n",
    "            tmp = []\n",
    "            for _ in range(len(deque)):\n",
    "                node= deque.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:deque.append(node.left)\n",
    "                if node.right:deque.append(node.right)\n",
    "            res.append(tmp[::-1] if len(res) % 2 else tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res=[]\n",
    "        deque=[root]\n",
    "        res.append(deque)\n",
    "        level=0\n",
    "        while True:\n",
    "            tmp=[]\n",
    "            for i in range(len(res[level])):\n",
    "                # if level%2==0:\n",
    "                #     root=res[level][i]\n",
    "                #     if root.right:\n",
    "                #         tmp.append(root.right)\n",
    "                #     if root.left:\n",
    "                #         tmp.append(root.left)\n",
    "                #     res[level][i]=root.val\n",
    "                # else:\n",
    "                #     root=res[level][-1-i]\n",
    "                #     if root.left:\n",
    "                #         tmp.append(root.left)\n",
    "                #     if root.right:\n",
    "                #         tmp.append(root.right)\n",
    "                #     res[level][-1-i]=root.val\n",
    "                root=res[level][-1-i]\n",
    "                if level%2==0:\n",
    "                    if root.right:\n",
    "                        tmp.append(root.right)\n",
    "                    if root.left:\n",
    "                        tmp.append(root.left)\n",
    "                else:\n",
    "                    if root.left:\n",
    "                        tmp.append(root.left)\n",
    "                    if root.right:\n",
    "                        tmp.append(root.right)\n",
    "                res[level][-1-i]=root.val\n",
    "            if not tmp:\n",
    "                break\n",
    "            res.append(tmp)\n",
    "            level+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # BFS+列表逆序\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()  # 先进先出\n",
    "                tmp.append(node.val)  # 顺序添加\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp[::-1] if len(res)%2 else tmp)  # 根据层数逆序\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        queue = deque()\n",
    "        res = []\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        queue.append(root)\n",
    "\n",
    "        i = 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            i +=1\n",
    "\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                tmp.append(cur.val)\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            print(i)\n",
    "            j = 1 if i%2 ==1 else -1\n",
    "            res.append(tmp[::j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [],collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = collections.deque()\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if len(res)%2 == 0: tmp.append(node.val)\n",
    "                else: tmp.appendleft(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, deque = [], collections.deque([root])\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if len(res) % 2 == 0: tmp.append(node.val) # 奇数层 -> 插入队列尾部\n",
    "                else: tmp.appendleft(node.val) # 偶数层 -> 插入队列头部\n",
    "                if node.left: deque.append(node.left)\n",
    "                if node.right: deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None: return []\n",
    "        deque, res, count = collections.deque(), [], 1\n",
    "        deque.append(root)\n",
    "        while deque:\n",
    "            tmp = []\n",
    "            for i in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left is not None:\n",
    "                    deque.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    deque.append(node.right)\n",
    "            if count & 1 == 0: tmp.reverse()\n",
    "            res.append(tmp)\n",
    "            count += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        k = 0\n",
    "        while queue:\n",
    "            # 定义队列\n",
    "            tmp = collections.deque()      # 队列有append()和appendleft()增添元素的方法\n",
    "            for _ in range(len(queue)):\n",
    "                newroot = queue.popleft()\n",
    "                if k & 1 == 0:             # 偶数层，从左到右添加元素\n",
    "                    tmp.append(newroot.val)\n",
    "                else:                      # 奇数层，从右到左添加元素\n",
    "                    tmp.appendleft(newroot.val)\n",
    "                if newroot.left:\n",
    "                    queue.append(newroot.left)\n",
    "                if newroot.right:\n",
    "                    queue.append(newroot.right)\n",
    "            k += 1\n",
    "            res.append(list(tmp))    # 将队列转化为列表，增加到res列表后\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        k = 0\n",
    "        while queue:\n",
    "            tmp = deque()\n",
    "            for _ in range(len(queue)):\n",
    "                newroot = queue.popleft()\n",
    "                if k & 1 == 0:\n",
    "                    tmp.append(newroot.val)\n",
    "                else:\n",
    "                    tmp.appendleft(newroot.val)\n",
    "                if newroot.left:\n",
    "                    queue.append(newroot.left)\n",
    "                if newroot.right:\n",
    "                    queue.append(newroot.right)\n",
    "            k += 1\n",
    "            res.append(list(tmp))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        '''\n",
    "        二叉树的层序遍历\n",
    "        '''\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        # 1-从左向右；0-从右向左\n",
    "        flag = True\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            tmp = []\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if not flag:\n",
    "                tmp.reverse()\n",
    "            res.append(tmp)\n",
    "            flag = not flag\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ans = []\n",
    "        q = deque([root])\n",
    "        even = False\n",
    "        while q:\n",
    "            vals = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                vals.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            ans.append(vals[::-1] if even else vals)\n",
    "            even = not even\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = deque()\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if len(res) % 2 == 0:\n",
    "                    tmp.append(node.val)\n",
    "                else:\n",
    "                    tmp.appendleft(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "# list 模拟queue\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        q = []\n",
    "        q.append(root)\n",
    "        tmp=[]\n",
    "\n",
    "        while len(q)!=0:\n",
    "            qsize = len(q)\n",
    "\n",
    "            for i in range(qsize):\n",
    "                node_tmp = q.pop(0)\n",
    "                tmp.append(node_tmp.val)\n",
    "\n",
    "                if node_tmp.left:\n",
    "                    q.append(node_tmp.left)\n",
    "                if node_tmp.right:\n",
    "                    q.append(node_tmp.right)\n",
    "\n",
    "            tmp = tmp[::-1] if len(res)&1 else tmp\n",
    "            res.append(tmp)\n",
    "            tmp = []\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "import queue\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        q = queue.Queue()\n",
    "        q.put(root)\n",
    "        tmp=[]\n",
    "\n",
    "        while not q.empty():\n",
    "            qsize = q.qsize()\n",
    "\n",
    "            for i in range(qsize):\n",
    "                node_tmp = q.get()\n",
    "                tmp.append(node_tmp.val)\n",
    "\n",
    "                if node_tmp.left:\n",
    "                    q.put(node_tmp.left)\n",
    "                if node_tmp.right:\n",
    "                    q.put(node_tmp.right)\n",
    "\n",
    "            tmp = tmp[::-1] if len(res)&1 else tmp\n",
    "            res.append(tmp)\n",
    "            tmp = []\n",
    "        return res\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        node_ls = [root, 1]\n",
    "        tmp = []\n",
    "        while node_ls:\n",
    "            node = node_ls.pop(0)\n",
    "            tmp.append(node.val)\n",
    "            if node.left is not None:\n",
    "                node_ls.append(node.left)\n",
    "            if node.right is not None:\n",
    "                node_ls.append(node.right)\n",
    "            if node_ls[0] == 1:\n",
    "                res.append(tmp)\n",
    "                tmp = []\n",
    "                node_ls.pop(0)\n",
    "                if not node_ls:\n",
    "                    break\n",
    "                node_ls.append(-1)\n",
    "            if node_ls[0] == -1:\n",
    "                res.append(tmp[::-1])\n",
    "                tmp = []\n",
    "                node_ls.pop(0)\n",
    "                if not node_ls:\n",
    "                    break\n",
    "                node_ls.append(1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        ret = []\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            ret.append([])\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "                ret[-1].append(node.val)\n",
    "            queue = tmp[:]\n",
    "            if len(ret) % 2 == 0:\n",
    "                ret[-1] = ret[-1][::-1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root == None: return []\n",
    "        tmp = []\n",
    "        tmp.append([root, 0])\n",
    "        ans, res = [], []\n",
    "        level, forward = 0, 0  # 0:当前层从左到右，1：当前层从右到左\n",
    "        while tmp:\n",
    "            cur = tmp.pop(0)\n",
    "            # print(cur, level)\n",
    "            if cur[1] != level:\n",
    "                if level %2 == 0:\n",
    "                    ans.append(res)\n",
    "                else:\n",
    "                    ans.append(res[::-1])\n",
    "                level += 1\n",
    "                res = [cur[0].val]\n",
    "            else:\n",
    "                res.append(cur[0].val)\n",
    "\n",
    "            if cur[0].left:\n",
    "                tmp.append([cur[0].left, level + 1])\n",
    "            if cur[0].right:\n",
    "                tmp.append([cur[0].right, level + 1])\n",
    "        if level % 2 == 0:\n",
    "            ans.append(res)\n",
    "        else:\n",
    "            ans.append(res[::-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        ans, n = [], 1\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            pre = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                pre.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            ans.append(pre[::n])\n",
    "            n *= -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res, queue = [], deque()\n",
    "        if not root:return res\n",
    "        queue.append(root)\n",
    "        flag = True\n",
    "        while queue:\n",
    "            \n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if flag:\n",
    "                res.append(tmp)\n",
    "                flag = False\n",
    "            else:\n",
    "                res.append(tmp[::-1])\n",
    "                flag = True\n",
    "            \n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        queue=[root]\n",
    "        if not root:\n",
    "            return []\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            res.append([])\n",
    "            for i in range(length):\n",
    "                root=queue[0]\n",
    "                queue.remove(queue[0])\n",
    "                res[-1].append(root.val)\n",
    "                if root.left:\n",
    "                    queue.append(root.left)\n",
    "                if root.right:\n",
    "                    queue.append(root.right)\n",
    "        for i in range(len(res)):\n",
    "            if i %2==1:\n",
    "                res[i]=res[i][::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, deque = [], collections.deque([root])\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if len(res) % 2 == 0: tmp.append(node.val) # 奇数层 -> 插入队列尾部\n",
    "                else: tmp.appendleft(node.val) # 偶数层 -> 插入队列头部\n",
    "                if node.left: deque.append(node.left)\n",
    "                if node.right: deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp[::-1] if len(res) % 2 else tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res, queue = [], deque()\n",
    "        if not root:return res\n",
    "        queue.append(root)\n",
    "        flag = True\n",
    "        while queue:\n",
    "            \n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if flag:\n",
    "                res.append(tmp)\n",
    "            else:\n",
    "                res.append(tmp[::-1])\n",
    "            flag=1-flag\n",
    "            \n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root):\n",
    "        a = True\n",
    "        if not root:\n",
    "            return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if a:\n",
    "                    if node.left:\n",
    "                        queue.append(node.left)\n",
    "                    if node.right:\n",
    "                        queue.append(node.right)\n",
    "                else:\n",
    "                    if node.right:\n",
    "                        queue.append(node.right)\n",
    "                    if node.left:\n",
    "                        queue.append(node.left)\n",
    "            a = not a\n",
    "            queue.reverse()\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, deque = [], collections.deque([root])\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if len(res) % 2 == 0: tmp.append(node.val) # 奇数层 -> 插入队列尾部\n",
    "                else: tmp.appendleft(node.val) # 偶数层 -> 插入队列头部\n",
    "                if node.left: deque.append(node.left)\n",
    "                if node.right: deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        stack = collections.deque()\n",
    "        stack.append(root)\n",
    "        while stack:\n",
    "            temp = collections.deque()\n",
    "            for _ in range(len(stack)):\n",
    "                node = stack.popleft()\n",
    "                if len(ans)%2 == 0 :\n",
    "                    temp.append(node.val)\n",
    "                else :\n",
    "                    temp.appendleft(node.val)\n",
    "\n",
    "                if node.left :\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            ans.append(list(temp))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        flag = 1\n",
    "        while queue:\n",
    "            layer = deque()\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if flag:\n",
    "                    layer.append(node.val)\n",
    "                else:\n",
    "                    layer.appendleft(node.val) \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(list(layer))\n",
    "            flag = 1 - flag\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,q=[],deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            temp=deque()\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                if len(res)%2==0:\n",
    "                    temp.append(node.val)\n",
    "                else:\n",
    "                    temp.appendleft(node.val)\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)         \n",
    "            res.append(list(temp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "\n",
    "        res, queue, flag = [], collections.deque(), True\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            if flag:  # 从左到右\n",
    "                for _ in range(len(queue)):\n",
    "                    node = queue.popleft()\n",
    "                    tmp.append(node.val)\n",
    "                    if node.left: queue.append(node.left)\n",
    "                    if node.right: queue.append(node.right)\n",
    "            else: # 从右到左\n",
    "                for _ in range(len(queue)):\n",
    "                    node = queue.pop()\n",
    "                    tmp.append(node.val)\n",
    "                    if node.right: queue.appendleft(node.right)\n",
    "                    if node.left: queue.appendleft(node.left)\n",
    "\n",
    "            res.append(tmp)\n",
    "            flag = not flag\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:return []\n",
    "        res,deque=[],collections.deque()\n",
    "        deque.append(root)\n",
    "        while deque:\n",
    "            tmp = []\n",
    "            for _ in range(len(deque)):\n",
    "                node= deque.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:deque.append(node.left)\n",
    "                if node.right:deque.append(node.right)\n",
    "            res.append(tmp[::-1] if len(res) % 2 else tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, deque = [] , collections.deque([root])\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if len(res) % 2 == 0:tmp.append(node.val)\n",
    "              # 奇数层 -> 插入队列尾部\n",
    "                else : tmp.appendleft(node.val)\n",
    "                # 偶数层 -> 插入队列头部\n",
    "                if node.left: deque.append(node.left)\n",
    "                if node.right: deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root:\n",
    "            a = [root]\n",
    "        else:\n",
    "            return []\n",
    "        returnList = []\n",
    "        flag = 0\n",
    "        while a:\n",
    "            n = len(a)\n",
    "            currenLevel = [i.val for i in a]\n",
    "            if flag==1:\n",
    "                currenLevel.reverse()\n",
    "            flag = 1- flag\n",
    "            for i in range(n):\n",
    "                node = a.pop(0)\n",
    "                if node.left: \n",
    "                    a.append(node.left)\n",
    "                if node.right: \n",
    "                    a.append(node.right)\n",
    "            returnList.append(currenLevel)\n",
    "        return returnList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        ans=[]\n",
    "        flag=1\n",
    "        while len(q) !=0:\n",
    "            nodes=[]\n",
    "            tps=[]\n",
    "            while len(q)!=0:\n",
    "                node=q.popleft()\n",
    "                nodes.append(node)\n",
    "                tps.append(node.val)\n",
    "            if flag%2==1:\n",
    "                ans.append(tps)\n",
    "            else:\n",
    "                ans.append(tps[::-1])\n",
    "            flag+=1\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        i=0\n",
    "        while queue:\n",
    "            temp = collections.deque()\n",
    "            for _ in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                if i%2==0:                    \n",
    "                   temp.append(node.val)\n",
    "                else:                                        \n",
    "                   temp.appendleft(node.val)        \n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right:queue.append(node.right)\n",
    "                          \n",
    "            res.append(list(temp))\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        direction = True\n",
    "\n",
    "        while queue:\n",
    "            tmp = []\n",
    "\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(tmp if direction else tmp[::-1])\n",
    "            direction = not direction\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        reverse = False\n",
    "        ans = []\n",
    "        if root is None: return ans\n",
    "        q = [root]\n",
    "        while q:\n",
    "            nxt = []\n",
    "            level = []\n",
    "            for node in q:\n",
    "                if node.left: nxt.append(node.left)\n",
    "                if node.right: nxt.append(node.right)\n",
    "                level.append(node.val)\n",
    "            if reverse:\n",
    "                level.reverse()\n",
    "            reverse = not reverse\n",
    "            ans.append(level)\n",
    "            q = nxt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        res = []\n",
    "        direction = True\n",
    "        while q:\n",
    "            temp = collections.deque()\n",
    "            for _ in range(len(q)):\n",
    "                node: TreeNode = q.popleft()\n",
    "                if direction:\n",
    "                    temp.append(node.val)\n",
    "                else:\n",
    "                    temp.appendleft(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            direction = not direction\n",
    "            res.append(list(temp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        from collections import deque\n",
    "        ret, queue = [], deque()\n",
    "        queue.append(root)\n",
    "        flag = 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            n = len(queue)\n",
    "            for _ in range(n):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if flag % 2 == 0:\n",
    "                ret.append(tmp)\n",
    "            else:\n",
    "                ret.append(tmp[::-1])\n",
    "            flag += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        flag = 1\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left: \n",
    "                    queue.append(node.left)\n",
    "                if node.right: \n",
    "                    queue.append(node.right)\n",
    "            if flag:\n",
    "                ans.append(temp)\n",
    "            else:\n",
    "                ans.append(list(reversed(temp)))\n",
    "            flag = 1 - flag\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        import queue\n",
    "        res = []\n",
    "        if not root: return res\n",
    "        q = queue.Queue()\n",
    "        q.put(root)\n",
    "        flag = True\n",
    "        while not q.empty():\n",
    "            n = q.qsize()\n",
    "            row = []\n",
    "            for i in range(n):\n",
    "                tmp = q.get()\n",
    "                row.append(tmp.val)\n",
    "                if tmp.left is not None:\n",
    "                    q.put(tmp.left)\n",
    "                if tmp.right is not None:\n",
    "                    q.put(tmp.right)\n",
    "            flag = not flag\n",
    "            if flag: row = row[::-1]\n",
    "            res.append(row)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        q = [root]\n",
    "        res = []\n",
    "        h = 1\n",
    "        while q:\n",
    "            ans = [node.val for node in q]\n",
    "            if h % 2 == 0:\n",
    "                res.append(ans[::-1])\n",
    "            else:\n",
    "                res.append(ans)\n",
    "            ll = []\n",
    "            for node in q:\n",
    "                if node.left:\n",
    "                    ll.append(node.left)\n",
    "                if node.right:\n",
    "                    ll.append(node.right)\n",
    "            q = ll\n",
    "            h += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp[::-1] if len(res)%2 else tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, deque = [], collections.deque([root])\n",
    "        while deque:\n",
    "            tmp = collections.deque()\n",
    "            for _ in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if len(res) % 2 == 0: tmp.append(node.val)\n",
    "                else: tmp.appendleft(node.val)\n",
    "                if node.left: deque.append(node.left)\n",
    "                if node.right: deque.append(node.right)\n",
    "            res.append(list(tmp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        ans, n = [], 1\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            pre = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                pre.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            ans.append(pre[::n])\n",
    "            n *= -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        q = [root]\n",
    "        flag = True\n",
    "        while q:\n",
    "            tmp_q = []\n",
    "            new_res = []\n",
    "            while q:\n",
    "                top_node = q.pop(0)\n",
    "                if top_node.left:\n",
    "                    tmp_q.append(top_node.left)\n",
    "                if top_node.right:\n",
    "                    tmp_q.append(top_node.right)\n",
    "                new_res.append(top_node.val)\n",
    "            q = tmp_q\n",
    "            if flag:\n",
    "                res.append(new_res)\n",
    "                flag = False\n",
    "            else:\n",
    "                res.append(new_res[::-1])\n",
    "                flag = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        if not root:\n",
    "            return ans\n",
    "        q=deque()\n",
    "        q.append(root)\n",
    "        sig=False\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            layer=[]\n",
    "            for i in range(n):\n",
    "                node=q.popleft()\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            if sig:\n",
    "                layer=layer[::-1]\n",
    "            sig=(not sig)\n",
    "            ans.append(layer)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # 简单层序遍历\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        count = 1\n",
    "        while q:\n",
    "            ans = []\n",
    "            count += 1\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                ans.append(node.val)\n",
    "                \n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            if count % 2 != 0:\n",
    "                res.append(ans[::-1])\n",
    "            else:\n",
    "                res.append(ans[:])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
